1. Field of the Invention
The present invention generally relates to content addressable memory devices, and more particularly, to a content addressable memory device which determines the top priority entry data by checking the length of valid data.
2. Description of the Related Art
A content addressable memory device (CAM) is a memory device which determines, in response to a data input, an address storing data equal to the input data in a memory area, and outputs the address. The input data is called an entry key and the data stored in the address is called an entry data.
While an address input to an ordinary semiconductor memory device specifies unique data, data input to a CAM device does not always specify a unique address because a plurality of addresses in a CAM device may store data equal to the input data. In the case that a plurality of addresses store data equal to the input data, a CAM device determines an output address by checking not only data stored in the addresses but also a predetermined priority assigned to the data. An address which stores entry data having the highest priority is output.
However, the priority is generally assigned to addresses, instead of data, and an address having the highest priority is output. The highest priority is, for example, assigned to the lowest address and a higher address has a lower priority. If a plurality of entry data is equal to an entry key, the lowest address storing an entry data equal to the entry key is determined and output.
Under the configuration described above, if new entry data having a predetermined priority is to be added to an existing entry data set, the new entry data must be inserted into the existing entry data arranged in the order of priority. For example, if new entry data having the third priority is to be added to an existing entry data set, an address to store the new entry data must be secured by shifting entry data stored in addresses higher than the third address to the next addresses. In this manner, new entry data must be stored in an address secured for the new entry data by shifting a part of an existing entry data set which is necessary to be shifted in an address space.
As described above, a method in which a priority is assigned to an address instead of entry data and entry data is stored in the address having the priority, will exhibit a low performance because a part of the entry data set must be shifted when new entry data is inserted into the entry data set.
Accordingly, it is a general object of the present invention to provide a novel and useful content addressable memory in which one or more of the problems described above are eliminated.
Another and more specific object of the present invention is to provide a content addressable memory which can determine entry data having the top priority without assigning priorities to addresses.
A content addressable memory device according to the present invention includes ternary cells which are arranged in rows and columns, and each stores therein xe2x80x9c0xe2x80x9d, xe2x80x9c1xe2x80x9d, or invalid data, wherein both xe2x80x9c0xe2x80x9d and xe2x80x9c1xe2x80x9d are valid data, valid data detection circuits, each of which is provided for a corresponding one of the ternary cells, and longest-match detection circuits, each of which is provided for a corresponding one of the ternary cells, wherein a valid data detection circuit provided for a first ternary cell located at a given bit position in a first row informs a second ternary cell located at the given bit position on a second row of presence of valid data if the first ternary cell has valid data stored therein and if entry data of the first row matches an entry key, and a longest-match detection circuit provided for the second ternary cell located at the given bit position on the second row finds entry data of the second row to be invalid if the second ternary cell has invalid data stored therein and if the valid data detection circuit is informing the longest-match detection circuit of the presence of valid data.
Each ternary cell relative to the present invention is provided with a function of informing other ternary cells of the existence of valid data for determining the longest match entry data. By this informing function, the ternary cell informs other ternary cells at the same bit position that the ternary data stored in the ternary cell is valid if the entry data which the ternary cell contains to is identical to the entry key. Once the existence of valid data is reported, the other ternary cells at the same bit position determine if invalid data is stored in their cell, in which case the cell turns from a state indicating storage of identical data to another state indicating that no identical data is stored.
As described above, if the content of a cell is invalid data, and another cell at the same bit position stored valid data, the cell determines that the entry data of the cell is not the top priority entry data, and excludes its entry data from the top priority data candidates.
Other objects, features, and advantages of the present invention will become more apparent from the following detailed description when read in conjunction with the accompanying drawings.